5.1 Definitie, proprietati, model Listele duble sunt structuri de date dinamice care permit traversarea in ambele sensuri.
Fiecare element contine trei componente:
- un pointer care memoreaza adresa elementului precedent
- o structura de tipaticol sau un cimp in care se memoreaza informatia utila prelucrarii
- un pointer care memoreaza adresa elementului urmator din structura.
Lista dubla are doi pointeri pentru referirea elementelor ce o compun.
Un pointer pentru a referi elementele cand procesul de traversare se efectueaza de la stanga spre dreapta. Acest pointer refera la inceput primul element al listei duble, iar dupa terminarea traversarii refera ultimul element.
Un pinter care permite traversarea de la dreapta spre stanga. Acest pointer refera ultimil element din lista dubla. Dupa traversare, va referi primul element al listei.
....................
....................
....................
....................
....................
....................
....................
.................... revenire
5.2 Creare
Crearea listei duble presupune:
- alocare de zona de memorie
- initializarea campurilor corespunzatoare informatiei utile
- initializarea cu NULL a campurilor prev si next
- apelarea procedurii de adaugare element in lista dubla
- initializarea pointerului cu care se refera distinct ultimul element.
....................
....................
....................
....................
....................
....................
....................
.................... revenire
5.3 Traversare
Este operatia prin care se refera toate elementele, din aproape in aproape.
Daca traversarea se efectueaza de la stanga la dreapta va exista trecerea la urmatorul element folosind pointerul next.
daca traversarea se face de la dreapta spre stanga se foloseste pointerul prev.
....................
....................
....................
....................
....................
....................
....................
.................... revenire
5.4 Operatii Inserarea este operatia care pozitioneaza un element printre elementele din interiorul listei duble. Adaugarea corespunde initializarii campului next din ultimul element cu adresa unui nou element si initializarea campului prev din noul element cu adresa ultimului element existent din lista dubla. Noul element devine ultim element in lista dubla. Stergerea corespunde eliberarii legaturilor unui element din lista dubla, astfel incat elementele ramase sa fie traversabile, iar elementul eliberat sa fie dealocat. Cautarea corespunde operatiei de comparare de informatii utile astfel incat sa fie reperat un element din lista dubla care indeplineste o conditie data. In urma cautarii este returnata adresa elementului care indeplineste conditia. In cazul in care nu exista un astfel de element se returneaza NULL. Concatenarea a doua liste duble revine la a construi o singura lista tot dubla prin initializarea campului next a ultimului element din prima lista cu adresa primului element din a doua lista si incarcarea in prev din primul element al celei de a doua liste cu adresa ulti,ului element din prima lista.
....................
....................
....................
....................
....................
....................
....................
.................... revenire
5.5 Aplicatii complexe Cautarea rapida corespunde situatiei in care elementele listei duble contin numele si prenumele persoanelor ordonate alfabetic.
Se presupune ca numele persoanelor incep cu litere uniform distribuite.
Se construieste o lista dubla.
Pointerul pcplds memoreaza adresa primului element al listei duble. Referirea lui next cu acest pointer intr-o expresie asigura traversarea de la stanga la dreapta.
Pointerul pcpldd memoreaza adresa ultimului element al listei duble. Referirea lui prev cu acest pointer intr-o expresie asigura traversarea de la dreapta la stanga.
Algoritmul de cautare rapida presupune:
- extragerea primei litere a numelui persoane pentru care se face cautarea
- daca litera este A,B,C,D,E,F,G,H,I,J,K,L traversarea se efectueaza de la stanga la dreapta folosind pointerul pclds.
- daca litera cu care incepe numele este M,N,...,Z, tyraversarea se efectueaza de la dreapta la stanga folosind pointerul pcpdd.
....................
....................
....................
....................
....................
....................
....................
.................... revenire
5.6 Evaluari
Evaluarile presupun:
- calculul gradului de utilizare GU dat de relatia:
GU=x*Lg(info)/(LG(info)+Lg(pcplds)+Lg(pcldd)+Lg(next)+Lg(prev))
- numarul de comparari necesar gasirii elementului cautat.
Daca se considera o lista cu x elemente, avand cheile 1,2,3,4,...,2*x-2,2*x-1,2*x si treuie gasite toate elementele, dar ordinea de dispunere a cheilor de cautare este aleatoare, daca se lucreaza cu o lista simpla, numarul de comparari NCOMP esate:
NCOMP=2*x(2*x+1)/2
NCOMP=x(2*x+1)
Daca structura aleasa este o lista dubla, pointerul pcplds este folosit pentru a referi elementele cu cheile 1,2,3,...,x.
Pointerul pcpldd este folosit pentru a referi elementele din lista dubla care au cheile x+1, x+2,...., 2*x-2, 2*x-1, 2*x.
Numarul de comparari se obtine din:
- compararea pentru a vedea intervalul
- compararile de a identifica elementul in intervalul stang
NCOMPs=x(x+1)/2
- compararile pentru a vedea elementul din intervalul drept
NCOMPd=x(x+1)/2.
Numarul total de comparari DNCOMP este:
DNCOMP=2*x + NCOMPs + NCOMPd
adica
DNCOMP=x(x+3)
Se observa ca DNCOMP < NCOMP.
Inseamna ca utlizarea listei duble este mai eficienta.
....................
....................
....................
....................
....................
....................
....................
.................... revenire
